package main

import "fmt"

type Node struct {
	value int
	fb    int
	left  *Node
	right *Node
}

func printfTree(tree *Node, deep int) {
	fmt.Printf("value: %d, fb: %d\n", tree.value, tree.fb)
	if tree.left != nil {
		printfTree(tree.left, deep+1)
	}
	if tree.right != nil {
		printfTree(tree.right, deep+1)
	}
}

/**
 * LL型子树调整平衡
 */
func turnLL(root *Node) {
	root.fb = 0
	root.left.fb = 0
	oldRoot := *root
	*root = *root.left
	oldRoot.left = root.right
	root.right = &oldRoot
}

/**
 * LR型子树调整平衡
 */
func turnLR(root *Node) {
	oldRoot := *root
	oldRootLeftRight := *root.left.right
	if oldRootLeftRight.fb == 0 {
		oldRoot.fb = 0
		root.left.fb = 0
	} else if oldRootLeftRight.fb == 1 {
		oldRoot.fb = -1
		root.left.fb = 0
	} else {
		oldRoot.fb = 0
		root.left.fb = 1
	}
	oldRootLeftRight.fb = 0

	*root = oldRootLeftRight
	root.left = oldRoot.left
	root.left.right = oldRootLeftRight.left
	oldRoot.left = oldRootLeftRight.right
	root.right = &oldRoot

}

/**
 * RR型子树调整平衡
 */
func turnRR(root *Node) {
	root.fb = 0
	root.right.fb = 0
	oldRoot := *root
	*root = *root.right
	oldRoot.right = root.left
	root.left = &oldRoot
}

/**
 * RL型子树调整平衡
 */
func turnRL(root *Node) {
	oldRoot := *root
	oldRootRightLeft := *root.right.left

	if oldRootRightLeft.fb == 0 {
		oldRoot.fb = 0
		root.right.fb = 0
	} else if oldRootRightLeft.fb == 1 {
		oldRoot.fb = 0
		root.right.fb = -1
	} else {
		oldRoot.fb = -1
		root.right.fb = 0
	}
	oldRootRightLeft.fb = 0

	*root = oldRootRightLeft
	root.right = oldRoot.right
	root.right.left = oldRootRightLeft.right
	oldRoot.right = oldRootRightLeft.left
	root.left = &oldRoot

}

/**
 * 树中插入节点
 */
func insert(root *Node, value int) bool {
	if root.value > value {
		if root.left == nil {
			root.left = createNode(value)
			root.fb++
			return root.right == nil //右子树不存在时，深度增加
		} else {
			if insert(root.left, value) {
				root.fb++
				if root.fb > 1 {
					if root.left.fb > 0 {
						turnLL(root)
					} else if root.left.fb < 0 {
						turnLR(root)
					}
				}
				return root.fb > 0
			}
		}
	} else if root.value < value {
		if root.right == nil {
			root.right = createNode(value)
			root.fb--
			return root.left == nil //左子树不存在时深度增加
		} else {
			if insert(root.right, value) {
				root.fb--
				if root.fb < -1 {
					if root.right.fb < 0 {
						turnRR(root)
					} else if root.right.fb > 0 {
						turnRL(root)
					}
				}
				return root.fb < 0
			}
		}
	}
	return false
}

func createNode(value int) *Node {
	newNode := new(Node)
	newNode.value = value
	newNode.fb = 0
	return newNode
}

func main() {
	//testLL()
	//testLL2()
	//testLL3()
	//testLR()
	//testLR2()
	//testRR()
	//testRL()
	testInsert()
}
